#include <vector>
using namespace std;
/*
 * @lc app=leetcode.cn id=74 lang=cpp
 *
 * [74] 搜索二维矩阵
 */

// @lc code=start
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int l = 0, r = m * n - 1; // [ ] 4 5
        while (r >= l) {
            int middle = (l + r) / 2;
            int row = middle / n, column = middle % n;
            if (matrix[row][column] == target) return true;
            else if (matrix[row][column] < target) l = middle + 1;
            else r = middle - 1; 
        }
        return false;
    }
};
// @lc code=end

